import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86186
 * Date: 2023-07-16
 * Time: 18:43
 */
public class Sort {

    // 直接插入排序
    class Solution {
        public int[] sortArray(int[] nums) {
            for(int i = 1; i < nums.length; i++) {
                int key = nums[i];
                int j = 0;
                for(j = i - 1; j >= 0; j--) {
                    if(nums[j] > key) {
                        nums[j+1] = nums[j];
                    }else {
                        break;
                    }
                }
                nums[j+1] = key;
            }
            return nums;
        }


        private void swap(int[] nums,int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }

// 希尔排序
    class Solution {
        public int[] sortArray(int[] nums) {
            int gap = nums.length;
            while(gap > 1) {
                gap /= 2;
                for(int i = 0; i < nums.length-gap; i++) {
                    int tmp = nums[i + gap];
                    int j = 0;
                    for(j = i; j >= 0; j -= gap) {
                        if(nums[j] > tmp) {
                            nums[j + gap] = nums[j];
                        }else {
                            break;
                        }
                    }
                    nums[j + gap] = tmp;
                }
            }
            return nums;
        }

        private void swap(int[] nums,int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }

// 选择排序
    class Solution {
        public int[] sortArray(int[] nums) {
            int left = 0;
            int right = nums.length-1;
            while(left < right) {
                int minIndex = left;
                int maxIndex = left;
                for(int i = left + 1; i <= right; i++) {
                    if(nums[i] < nums[minIndex]) {
                        minIndex = i;
                    }
                    if(nums[i] > nums[maxIndex]) {
                        maxIndex = i;
                    }
                }
                swap(nums,left,minIndex);
                if(maxIndex == left) {
                    maxIndex = minIndex;
                }
                swap(nums,right,maxIndex);
                left++;
                right--;
            }
            return nums;
        }


        private void swap(int[] nums,int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }

// 堆排序
    class Solution {
        public int[] sortArray(int[] nums) {
            createHeap(nums);
            int len = nums.length-1;
            for(int i = 0; i < nums.length; i++) {
                swap(nums,0,len);
                len--;
                shiftDown(nums,0,len);
            }
            return nums;
        }


        private void createHeap(int[] nums) {
            for(int p = (nums.length-1-1)/2; p >= 0; p--) {
                shiftDown(nums,p,nums.length-1);
            }
        }


        private void shiftDown(int[] nums,int parent, int len) {
            int child = 2 * parent + 1;
            while(child <= len) {
                if(child + 1 <= len && nums[child + 1] > nums[child]) {
                    child++;
                }
                if(nums[parent] < nums[child]) {
                    swap(nums,parent,child);
                    parent = child;
                    child = 2 * parent + 1;
                }else {
                    break;
                }
            }
        }


        private void swap(int[] nums,int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }

// 冒泡排序
    class Solution {
        public int[] sortArray(int[] nums) {
            for(int i = 0; i < nums.length-1; i++) {
                boolean flg = false;
                for(int j = 0; j < nums.length-i-1; j++) {
                    if(nums[j] > nums[j+1]) {
                        swap(nums,j,j+1);
                        flg = true;
                    }
                }
                if(!flg) break;
            }
            return nums;
        }



        private void swap(int[] nums,int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }

// horea 版 快速排序
    class Solution {
        public int[] sortArray(int[] nums) {
            quickSort(nums,0,nums.length-1);
            return nums;
        }


        private void quickSort(int[] nums,int left, int right) {
            if(left >= right) return;
            if(right - left < 10) {
                insertSort(nums);
                return;
            }
            int pivot = getPivot(nums,left,right);
            quickSort(nums,left,pivot-1);
            quickSort(nums,pivot+1,right);
        }


        private void insertSort(int[] nums) {
            for(int i = 1; i < nums.length; i++) {
                int key = nums[i];
                int j = 0;
                for(j = i - 1; j >= 0; j--) {
                    if(nums[j] > key) {
                        nums[j+1] = nums[j];
                    }else {
                        break;
                    }
                }
                nums[j+1] = key;
            }
        }


        private int getPivot(int[] nums,int left,int right) {
            int key = nums[left];
            int tmp = left;
            while(left < right) {
                while(left < right && nums[right] >= key) {
                    right--;
                }
                while(left < right && nums[left] <= key) {
                    left++;
                }
                swap(nums,left,right);
            }
            swap(nums,left,tmp);


            return left;
        }



        private void swap(int[] nums,int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }

// 挖坑法
    class Solution {
        public int[] sortArray(int[] nums) {
            quickSort(nums,0,nums.length-1);
            return nums;
        }


        private void quickSort(int[] nums,int left, int right) {
            if(left >= right) return;
            if(right - left < 10) {
                insertSort(nums);
                return;
            }
            int pivot = getPivot(nums,left,right);
            quickSort(nums,left,pivot-1);
            quickSort(nums,pivot+1,right);
        }


        private void insertSort(int[] nums) {
            for(int i = 1; i < nums.length; i++) {
                int key = nums[i];
                int j = 0;
                for(j = i - 1; j >= 0; j--) {
                    if(nums[j] > key) {
                        nums[j+1] = nums[j];
                    }else {
                        break;
                    }
                }
                nums[j+1] = key;
            }
        }


        private int getPivot(int[] nums,int left,int right) {
            int key = nums[left];
            while(left < right) {
                while(left < right && nums[right] >= key) {
                    right--;
                }
                nums[left] = nums[right];
                while(left < right && nums[left] <= key) {
                    left++;
                }
                nums[right] = nums[left];
            }
            nums[left] = key;


            return left;
        }



        private void swap(int[] nums,int i, int j) {
            int tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
    }

// 非递归快排
public int[] sortArray2(int[] nums) {
    Stack<Integer> stack = new Stack<>();
    int left = 0;
    int right = nums.length-1;
    int pivot = getPivot(nums,left,right);
    if(pivot - 1 > left) {
        stack.push(left);
        stack.push(pivot-1);
    }
    if(pivot + 1 < right) {
        stack.push(pivot + 1);
        stack.push(right);
    }
    while(!stack.isEmpty()) {
        right = stack.pop();
        left = stack.pop();
        pivot = getPivot(nums,left,right);

        if(pivot - 1 > left) {
            stack.push(left);
            stack.push(pivot-1);
        }
        if(pivot + 1 < right) {
            stack.push(pivot + 1);
            stack.push(right);
        }
    }
    return nums;
}



    private int getPivot1(int[] nums,int left,int right) {
        int key = nums[left];
        while(left < right) {
            while(left < right && nums[right] >= key) {
                right--;
            }
            nums[left] = nums[right];
            while(left < right && nums[left] <= key) {
                left++;
            }
            nums[right] = nums[left];
        }
        nums[left] = key;


        return left;
    }



    private void swap1(int[] nums,int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

// 前后指针法
public int[] sortArray1(int[] nums) {
    quick(nums,0,nums.length-1);
    return nums;
}


    private void quick(int[] nums, int left, int right) {
        if(left >= right) return;
        int pivot = getPivot(nums,left,right);
        quick(nums,left,pivot-1);
        quick(nums,pivot+1,right);
    }



    private int getPivot(int[] nums, int left, int right) {
        int key = nums[left];
        int prev = left;
        int cur = left + 1;
        while(cur <= right) {
            if(nums[cur] < key && nums[++prev] != nums[cur]) {
                swap(nums,prev,cur);
            }
            cur++;
        }
        swap(nums,left,prev);
        return prev;
    }


    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

// 归并排序
public int[] sortArray(int[] nums) {
    mergeSort(nums,0,nums.length-1);
    return nums;
}


    private void mergeSort(int[] nums, int left, int right) {
        if(left >= right) return;
        int mid = left + (right - left) / 2;
        mergeSort(nums,left,mid);
        mergeSort(nums,mid+1,right);
        merge(nums,left,right,mid);
    }


    private void merge(int[] nums, int left, int right,int mid) {
        int[] tmp = new int[right - left + 1];
        int s1 = left;
        int s2 = mid + 1;
        int k = 0;
        while (s1 <= mid && s2 <= right) {
            if(nums[s2] <= nums[s1]) {
                tmp[k++] = nums[s2++];
            }else {
                tmp[k++] = nums[s1++];
            }
        }
        while (s1 <= mid) {
            tmp[k++] = nums[s1++];
        }
        while (s2 <= right) {
            tmp[k++] = nums[s2++];
        }
        for (int i = 0; i < tmp.length; i++) {
            nums[i+left] = tmp[i];
        }
    }
}
